package net.tp.algo.permute;

import java.util.*;
import java.util.function.*;
import static net.tp.util.Utils.*;


/**
 * Heap Permutation.
 *
 * <p>Heap permutation is an exchange-based approach. It's running time is $O(N!)$.
 *
 *
 * <pre>
 *   ───┬──────────────
 *   ───┴──────────────
 * </pre>
 *
 *
 *
 * @time $O(N!)$
 *
 */
public class HeapPermutation {

    public static void permute(String a, Consumer<char[]> consumer) {
        permute(toCharArray(a), consumer);
    }

    public static void permute(char[] a, Consumer<char[]> consumer) {
        permute(a, a.length, consumer);
    }

    private static void permute(char[] a, int n, Consumer<char[]> consumer) {
        if (n == 1) {
            consumer.accept(a);
        }
        else {
            for (int i = 0; i < n; i++) {
                permute(a, n-1, consumer);
                if (n % 2 == 1) swap(a, 0, n-1);
                else swap(a, i, n-1);
            }
        }
    }

    private static void swap(char[] a, int i, int j) {
        char tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

}
